/*
 * Nancy Qiannan Zhang
 * Andrew ID: qiannanz
 * 
 * Mita Yipeng Yun
 * Andrew ID: yipengy
 */

package edu.cmu.cs211.bacon.util;

import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;

/**
 * A base to help implement a directed graph
 */
public class GeneralGraph<V,E extends Edge<V>> implements Graph<V,E> {

	//the map contains vertex as key and collection of edges as value
	HashMap<V, HashMap<V,E>> map;
	/**
	 * Creates an empty graph.
	 */
	public GeneralGraph()
	{
		map = new HashMap<V,HashMap<V,E>>();
	}

	/**
	 * Creates a graph with pre-defined vertices.
	 * 
	 * @param vertices
	 *            A list of the vertices in the graph.
	 * @throws NullPointerException
	 *             If vertices is null, or contains null items
	 */
	public GeneralGraph (Collection<? extends V> vertices)
	{
		if(vertices == null)
			throw new NullPointerException();
		map = new HashMap<V,HashMap<V,E>>(vertices.size());
		Iterator<? extends V> itr =vertices.iterator();
		//iterate through the given collection of vertices to add to map and set
		while(itr.hasNext()){
			V temp = itr.next();
			map.put(temp,new HashMap<V,E>());
		}
	}

	/**
	 * Creates a graph with pre-defined edges and vertices.
	 * 
	 * @param vertices
	 *            A list of the vertices in the graph.
	 * @param edges
	 * 			  A list of edges for the graph.
	 * @throws IllegalArgumentException if edges contains invalid edges.
	 * @throws NullPointerException
	 *             If vertices or edges is null, or either contain null items
	 */
	public GeneralGraph (Collection<? extends V> vertices, Collection<? extends E> edges)
	{
		if(vertices == null || edges == null)
			throw new NullPointerException();
		int size = vertices.size();
		map = new HashMap<V,HashMap<V,E>>(size);
		Iterator<? extends V> itr =vertices.iterator();
		//iterate through vertices to add to the map and set
		while(itr.hasNext()){
			V temp = itr.next();
			map.put(temp,new HashMap<V,E>());
		}
		Iterator<? extends E> e_itr = edges.iterator();
		//iterate through edges to add to the map
		while(e_itr.hasNext()){
			E temp = e_itr.next();
			//cannot have edges that connect to invalid vertex
			if(!(vertices.contains(temp.src())&&vertices.contains(temp.dest())))
				throw new IllegalArgumentException();
			//cannot have edges that connect vertex to itself
			if(temp.src().equals(temp.dest()))
				throw new IllegalArgumentException();
			map.get(temp.src()).put(temp.dest(),temp);
		}
	}

	/**
	 * Copy Constructor
	 * 
	 * @param g
	 *            A graph to copy
	 * @throws IllegalArgumentException if g violates Graph invariants by
	 *            returning illegal edges in its outgoingEdge methods
	 * @throws NullPointerException
	 *             If g is null, or g's methods violates Graph invariants
	 *             by returning null items in verticies or outgoingEdges
	 */
	public GeneralGraph (Graph <V, E> g)
	{
		if(g == null || g.vertices() == null)
			throw new NullPointerException();
		int size = g.vertices().size();
		map = new HashMap<V,HashMap<V,E>>(size);
		for(V temp:g.vertices()){
			Collection<E> edges = g.outgoingEdges(temp);
			if(edges== null)
				throw new NullPointerException();
			HashMap<V,E> edgeMap = new HashMap<V,E>();
			for(E edge :edges){
				if(edge.src().equals(edge.dest()) || !g.vertices().contains(edge.dest()))
					throw new IllegalArgumentException();
				edgeMap.put(edge.dest(), edge);
			}
			map.put(temp,edgeMap);
		}
	}

	/**
	 * Add a vertex to the graph.
	 * @param vertex The vertex to add
	 * @throws NullPointerException if vertex is null.
	 * @return true if vertex was not present already.
	 */
	public boolean addVertex(V vertex)
	{
		if(vertex == null)
			throw new NullPointerException();
		//map already has this vertex
		if(map.containsKey(vertex))
			return false;
		int size = map.size()+1;
		//add to both set and map by creating a new map
		HashMap<V,HashMap<V,E>> temp = new HashMap<V,HashMap<V,E>>(size);
		temp.putAll(map);
		map = temp;
		map.put(vertex, new HashMap<V,E>());
		return true;
	}
	/**
	 * Adds multiple vertices to a graph.
	 * 
	 * @throws NullPointerException
	 *             if vertices is null, or any vertex is null.
	 * @return true if and only if the set of vertices was changed by the operation.
	 */
	public boolean addVertices(Collection<? extends V> vertices)
	{
		if(vertices == null)
			throw new NullPointerException();
		int size = map.size()+vertices.size();
		HashMap<V,HashMap<V,E>> temp_map = new HashMap<V,HashMap<V,E>>(size);
		temp_map.putAll(map);
		map = temp_map;
		Iterator<? extends V> itr =vertices.iterator();
		//iterate through, add to map and set
		while(itr.hasNext()){
			V temp = itr.next();
			if(temp == null)
				throw new NullPointerException();
			//map already has one of the vertices to be added
			if(map.containsKey(temp))
				return false;
			map.put(temp,new HashMap<V,E>());
		}
		return true;
	}
	/**
	 * Adds edge e to the graph.
	 * 
	 * @param e
	 *            The edge to add.
	 * @throws IllegalArgumentException
	 *             If e represents a self-transition or is otherwise not a valid edge (eg. refers to vertices not in the graph).
	 * @throws NullPointerException
	 *             If e is null
	 * @return true If e was not already present; false if it was (in which case the graph is not updated).
	 */
	public boolean addEdge (E e)
	{
		if(e == null)
			throw new NullPointerException();
		if(!this.vertices().contains(e.src()) || 
				!this.vertices().contains(e.dest()) ||
				e.src().equals(e.dest()))
			throw new IllegalArgumentException();
		//remove the previous mapping
		HashMap<V,E> edges= map.remove(e.src());
		if(edges.containsKey(e.dest())){
			map.put(e.src(), edges);
			return false;}
		edges.put(e.dest(),e);
		//put in the new edges to the map
		map.put(e.src(), edges);
		return true;
	}

	/**
	 * Adds multiple edges to a graph.
	 * 
	 * @throws NullPointerException
	 *             if edges is null or any edge in the list is null
	 * @throws IllegalArgumentException if any edge in the collection is invalid.
	 * @return true if and only if the set of edges was changed by the operation.
	 */
	public boolean addEdges (Collection<? extends E> edges)
	{
		if(edges == null)
			throw new NullPointerException();
		Iterator<? extends E> e_itr = edges.iterator();
		while(e_itr.hasNext()){
			this.addEdge(e_itr.next());

		}
		return true;
	}
	/**
	 * Remove an edge from src to dest from the graph.
	 * 
	 * @throws NullPointerException if src or dest is null.
	 * @throws IllegalArgumentException if src or dest is not in the graph.
	 * @return true If an edge from src to dest edge was present.
	 */
	public boolean removeEdge (V src, V dest)
	{
		if(src == null || dest == null)
			throw new NullPointerException();
		if(!this.vertices().contains(dest) || !this.vertices().contains(src))
			throw new IllegalArgumentException();
		HashMap<V,E> edges = map.remove(src);
		if(edges == null)
			return false;
		Edge<V> rmv = edges.remove(dest);
		map.put(src, edges);
		if(rmv == null)
			return false;
		return true;
	}
	/** Removes all edges from the graph */
	public void clearEdges ()
	{
		Set<V> temp = map.keySet();
		for(V next : temp)
			map.put(next, new HashMap<V,E>());
	}
	/**
	 * Returns a view of the set of vertices in the graph. The resulting set is
	 * immutable, and is updated when the graph itself is.
	 * @return The set of all vertices in the graph. 
	 */
	public Set<V> vertices ()
	{
		return map.keySet();
	}
	/**
	 * Tests if vertices i and j are connected, returning the edge between
	 * them if so.
	 * 
	 * @throws IllegalArgumentException if i or j are not vertices in the graph.
	 * @throws NullPointerException if i or j is null.
	 * @return The edge from i to j if it exists in the graph;
	 * 				null otherwise.
	 */
	public E connected (V i, V j)
	{
		if(i == null || j == null)
			throw new NullPointerException();
		if((!this.vertices().contains(i)) || (!this.vertices().contains(j)) )
			throw new IllegalArgumentException();
		return map.get(i).get(j);
	}
	/**
	 * Return the neighbours of a given vertex; that is, vertices to which
	 *     vertex has an outgoing edge. This set is immutable, and will change
	 *     when the vertex gets new neighbors (it is is backed by the graph)
	 * @param vertex The vertex the neighbours of which to return.
	 * @throws NullPointerException if vertex is null.
	 * @throws IllegalArgumentException if vertex is not in the graph.
	 * @return The set of neighbours of vertex.
	 */
	public Set<V> neighbors (V vertex)
	{
		if(vertex == null)
			throw new NullPointerException();
		if(!this.vertices().contains(vertex))
			throw new IllegalArgumentException();
		return map.get(vertex).keySet();
	}
	/**
	 * Returns the edges leaving vertex. The collection should be immutable.
	 * When edges are added to this vertex, the returned collection will change
	 * (it is a view backed by the graph)
	 * @param vertex The vertex the outgoing edges of which to return.
	 * @throws NullPointerException if vertex is null.
	 * @throws IllegalArgumentException if vertex is not in the graph.
	 * @return The set of edges leaving vertex.
	 */
	public Collection<E> outgoingEdges (V vertex)
	{
		if(vertex == null)
			throw new NullPointerException();
		if(!this.vertices().contains(vertex))
			throw new IllegalArgumentException();
		return map.get(vertex).values();
	}
}

